The creation of an image mosaic is a powerful analytical tool when observing large areas in fine detail. It is often necessary, when tracking ice drifts or the movement of geographical features, to mosaic multiple photographs with a common resolution, into a single image that shows the entire area of interest. These mosaics typically occur only in two dimensions, where the images are mosaicked only along the width and length of the image.
Integrated circuits (ICs) are sometimes analysed using similar techniques, in order that the IC may be reverse-engineered or examined for quality control. ICs are made up of multiple layers of semiconductor and metal, overlaid on top of one another in order to create interconnected circuitry. When analyzing these devices, multiple images of each layer of the IC are collected in a matrix pattern of rows and columns and then “stitched” together to form a mosaic. In performing the analysis, one can examine the mosaic of each layer of the IC, and understand the interconnections of the overall circuit. Alternatively, to save time, one can overlay partially transparent mosaics of each layer to more clearly understand the interconnections of the overall circuit. However, as there will be small errors between the layers in the alignment of the overlaid images in each mosaic, this may introduce errors in the analysis.
A procedure called pair-wise registration, which is a well-known technique in the art, is used to digitally stitch together the images on a common plane by minimizing registration errors. Pair-wise registration accomplishes this through calculation of the relative image coordinates of a pair of images, and the selection of a single pair of corresponding points between the two images. More images may be pair-wise registered by applying a similar technique to another image and the previously registered image pair. Such a registration can be performed by techniques described in the paper “A survey of image registration techniques” by L. Brown, ACM Computing Surveys, Vol 24, Issue 4, 1992, incorporated by reference herein.
Global image registration allows for the finding of relative coordinates of overlapped images, in order to compensate for errors introduced by the image acquisition system. When the images are globally registered, all of the images to be registered are manipulated until a registration is achieved that minimizes and distributes the registration errors between them and across each image. This can be done by, for example, using least squares energy minimization. The details of least squares based energy minimization are given in Chapter One of the Proceedings of Sixth Annual PIMS Industrial Problem Solving Workshop, 2002, Pacific Institute for Mathematical Sciences, which is incorporated by reference herein.
However, the prior art does not address several issues. In some cases, there is not enough information in the overlapping section of the images to define relative coordinates with enough precision. Alternatively, there may be no overlapping section, due to issues with the image acquisition system, or erroneous pair-wise registration. The presence of such erroneous relative coordinates adversely affects the quality of registration of large numbers of nearby images, as the error is distributed by the energy minimization procedure across the image.
Also, when different mosaics, showing the same area but in relation to different layers, are registered independently of one another, it may happen that error will be accumulated such that vertical alignment of these two mosaics would be impossible without changing the way they were registered, which the prior art does not consider.
As well, in the prior art, there is no way to collect human operator feedback or integrate inspection results as to the fit of the registration. Thus, should the results of the energy minimization approach be unacceptable, an operator may have to move a large number of images manually.
Therefore, a need exists in the art for an image-mosaicking algorithm that will compensate not only for registration errors within a single layer, but also alignment errors across multiple layers of the same area in an overlay configuration that will allow for inspection and correction of both the registration and alignment of the constituent images.